package leetcode;

import java.util.HashMap;

/**
 * Created by tiang on 2018/11/22.
 */
public class CloneRandomList {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode, RandomListNode> on = new HashMap<>();
        RandomListNode root = copySub(head, on);
        copySubRandom(head, root, on);
        return root;
    }

    /**
     * 先复制next节点
     * @param node 旧节点
     * @param old2new 新旧节点对应关系
     * @return 复制之后的列表
     */
    private RandomListNode copySub(RandomListNode node, HashMap<RandomListNode, RandomListNode> old2new){
        if(node == null)
            return null;
        if(old2new.containsKey(node))
            return old2new.get(node);
        RandomListNode newNode = new RandomListNode(node.label);
        old2new.put(node, newNode);
        newNode.next = copySub(node.next, old2new);
        return newNode;
    }

    /**
     * 复制random节点
     * @param oldNode 旧节点
     * @param newNode 新节点
     * @param old2New 新旧节点列表
     */
    private void copySubRandom(RandomListNode oldNode, RandomListNode newNode, HashMap<RandomListNode, RandomListNode> old2New){
        if(oldNode == null)
            return;
        RandomListNode rand = oldNode.random;
        if(old2New.containsKey(rand))
            newNode.random = old2New.get(rand);
        copySubRandom(oldNode.next, newNode.next, old2New);
    }
}
class RandomListNode {
    int label;
    RandomListNode next, random;

    RandomListNode(int x) {
        this.label = x;
    }
}